/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode*cur1=headA;
        ListNode*cur2=headB;
        int i=1,j=1;
        while(cur1->next)
        {
            i++;
            cur1=cur1->next;
        }
        while(cur2->next)
        {
            j++;
            cur2=cur2->next;
        }
        if(cur1!=cur2) return nullptr;
        if(i>j)
        {
            int count=i-j;
            while(count--)
            {
                headA=headA->next;
            }
        }
        if(i<j)
        {
            int count=j-i;
            while(count--)
            {
                headB=headB->next;
            }
        }

        while(headA)
        {
            if(headA==headB)return headA;

            headA=headA->next;
            headB=headB->next;
        }

        return nullptr;
        
    }
};
//进阶解法
class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        ListNode* p = headA;
        ListNode* q = headB;
        while (p != q) {
            p = p ? p->next : headB;
            q = q ? q->next : headA;
        }
        return p;
    }
};

